1. Column of the Invention
The invention relates to computer networks, and in particular, to media access control (MAC) address management.
2. Description of the Related Art
FIG. 1a shows a conventional MAC table. Conventionally, a typical router or switch establishes a MAC table in the memory to keep track of MAC addresses in streamed packets. A MAC table comprises a plurality of columns, such as first column 100, second column 102, third column 104 and fourth column 106, each capable of storing one MAC address. Addresses of every four columns also serve as indices for rapid access. For example, Index1 is an index for the columns 100, 102, 104 and 106.
FIG. 1b is a flowchart of a method for conventional MAC address management. If 2048 columns are provided in a memory block, 512 indices are therefore available each corresponding to four columns. In step S102, when a packet is received, the MAC address thereof is calculated according to a hash algorithm to obtain a corresponding index. Alternatively, the index may be directly obtained from the last 9 bits of the MAC address. In step S104, the MAC table is consulted to determine whether the MAC address is already stored in the corresponding four columns. If not, a learning procedure is processed in step S108 to update the MAC table with the MAC address. Conventionally, there exists an expiration time limit in every MAC address if there is no access to a MAC address for a period of time, and the MAC table eliminates the expired MAC address automatically. If the MAC address is already stored in a corresponding one of the four columns, the access time of the MAC address is updated to keep it from expiration in step S106.
FIG. 2a is a flowchart of a learning procedure for conventional MAC address. The procedure includes the following steps. In step S202, the corresponding four columns of the MAC table are checked according to the index generated by the MAC address. In step S204, it is individually checked whether the capacities of one of the four columns are available for the MAC address. If one of the columns is available, the MAC address is stored thereto in step S206. If all four columns are filled, one of the columns is overwritten in step S208. The principle for overwrite is that selecting a column to be overwritten if the expiration time limit of a column is almost reached. Alternatively, the four columns may be overwritten in turn or at random.
FIG. 2b shows a conventional MAC table. Index1, Index2 and Index3 each correspond to four columns. Among the columns with Index1, column 200 stores a MAC address (marked as learned), and the other three are empty. Columns 208, 210, 212 and 214 of Index2 are filled with MAC addresses (learned). When a new MAC address corresponding to Index2 is provided, the column 208 is overwritten. Therefore, the four columns corresponding to Index3 are empty.
Using indices to access the MAC addresses is convenient; however, the utilization of memory is not efficient. For example, overwrite is required if all columns with Index2 are filled with MAC addresses and one more MAC address of Index2 is provided. In fact, there are still a lot of free memory spaces such as columns with Index3. An enhancement is desirable to efficiently use all available memory resources.